#
# Bintree.pm : 二分探索木（オブジェクトのテスト）
#
# 格納するデータはオブジェクトであること
#
package Bintree;

# 終端を示す nil 用無名空ハッシュ
$nil = {};
bless $nil, 'Bintree';

# 二分木を空に初期化
sub make_tree { $nil; }

# 二分木の探索
sub search_tree {
  my ($node, $item) = @_;
  while( $node != $nil ){
    my $result = $item->compare( $node->{'item'} );
    if( $result == 0 ){
      return 1;
    } elsif( $result < 0 ){
      $node = $node->{'left'};
    } else {
      $node = $node->{'right'};
    }
  }
  0;
}
  
# データの追加
sub insert_tree {
  my ($node, $item) = @_;
  if( $node == $nil ){
    my $new = {'item' => $item, 'left' => $nil, 'right' => $nil };
    bless $new, 'Bintree';
    return $new;
  } else {
    my $result = $item->compare( $node->{'item'} );
    if( $result < 0 ){
      $node->{'left'} = &insert_tree( $node->{'left'}, $item );
    } elsif( $result > 0 ){
      $node->{'right'} = &insert_tree( $node->{'right'}, $item );
    }
  }
  $node;
}

# 二分木の表示
sub print_tree {
  my $node = shift;
  if( $node != $nil ){
    &print_tree( $node->{'left'} );
    $node->{'item'}->print_object();
    &print_tree( $node->{'right'} );
  }
}

# debug print
sub print_tree_test {
  my ($node, $level) = @_;
  my $i;
  if( $node != $nil ){
    &print_tree_test( $node->{'left'}, $level + 1 );
    for( $i = 0; $i < $level; $i++ ){
      print "  ";
    }
    $node->{'item'}->print_object();
    &print_tree_test( $node->{'right'}, $level + 1 );
  }
}


1;

# end of file

